package com.fw.leetcode.matrix;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 289. Game of Life
 *
 * According to Wikipedia's article: "The Game of Life, also known simply as Life,
 * is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
 *
 * The board is made up of an (m x n) grid of cells, where each cell has an initial state:
 * live (represented by a 1) or dead (represented by a 0).
 * Each cell interacts with its eight neighbors (horizontal, vertical, diagonal)
 * using the following four rules (taken from the above Wikipedia article):
 *
 * Any live cell with fewer than two live neighbors dies as if caused by under-population.
 * Any live cell with two or three live neighbors lives on to the next generation.
 * Any live cell with more than three live neighbors dies, as if by over-population.
 * Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
 *
 * The next state is created by applying the above rules simultaneously to every cell in the current state,
 * where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
 *
 * Example 1:
 *  Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
 *  Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
 *
 * Example 2:
 *  Input: board = [[1,1],[1,0]]
 *  Output: [[1,1],[1,1]]
 *
 * Constraints:
 *  m == board.length
 *  n == board[i].length
 *  1 <= m, n <= 25
 *  board[i][j] is 0 or 1.
 *
 * Follow up:
 *  Could you solve it in-place? Remember that the board needs to be updated simultaneously:
 *  You cannot update some cells first and then use their updated values to update other cells.
 *
 *  In this question, we represent the board using a 2D array.
 *  In principle, the board is infinite, which would cause problems when the active area
 *  encroaches upon the border of the array (i.e., live cells reach the border).
 *  How would you address these problems?
 */
public class Num_0289 implements LeetCode {

    private interface Solution {
        void gameOfLife(int[][] board);

        default void assertExpected(int[][] matrix, int[][] expected) {
            int[][] oldMatrix = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < oldMatrix.length; i++) {
                System.arraycopy(matrix[i], 0, oldMatrix[i], 0, oldMatrix[i].length);
            }
            gameOfLife(matrix);
            for (int i = 0; i < matrix.length; i++) {
                if (!Arrays.equals(matrix[i], expected[i])) {
                    gameOfLife(oldMatrix);
                }
            }
        }
    }

    private static class MySolution implements Solution {

        private int sum(int[][] board, int ci, int cj) {
            int sum = 0;
            for (int i = ci - 1; i <= ci + 1; i++) {
                for (int j = cj - 1; j <= cj + 1; j++) {
                    if ((i == ci && j == cj) // 去除原位元素
                      || i < 0 || i > board.length - 1
                      || j < 0 || j > board[i].length - 1) { // 去除边界不可达元素
                        continue;
                    }
                    sum += board[i][j];
                }
            }
            return sum;
        }

        @Override
        public void gameOfLife(int[][] board) { // 矩阵 + 原位标记（高位标记，延迟变更）：时O(mn) 空O(1)
            /*
             * 原位标记法：（mask 0x100）
             *
             * prev -> next = mark
             * 0       1      0x100
             * 1       0      0x101
             *
             * 第一轮遍历
             * 1.有需要变化的，第8位标记1，第0位不变
             * 2.周围8个数相加后，用 0xff 取低8位和（sum <= 8，不会影响到标记位）判断是死是活，再用mask标记
             * 第二轮遍历
             * 1.将所有有mask标记的元素去掉mask，0->1 1->0 变化
             * 结束
             */
            // 第一轮，原位标记是否需要变更状态
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    int alive = sum(board, i, j) & 0xff; // 取低8位，不含标记位（多个标记位相加依然在高位）
                    /*
                     * 当前是 死，(== 3) 可活重生         => [标记变更]
                     * 当前是 死，(!= 3) 不可活           => [不变]
                     * 当前是 活，(== 2|3) 时，可活至下一代 => [不变]
                     * 当前是 活，(!= 2|3) 渴死           => [标记变更]
                     */
                    if ((board[i][j] == 0 && alive == 3)
                        || (board[i][j] == 1 && (alive < 2 || alive > 3))) {
                        board[i][j] |= 0x100; // 标记待变更，即：延迟变更
                    }
                }
            }
            // 第二轮，将待变更的元素实现变更
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] > 1) { // 存在标记位，需变更
                        // 第0位+1效果，0->1 1->0，最后只保留第0位，即变更后的状态
                        board[i][j] = (board[i][j] + 1) & 0x1;
                    }
                }
            }
            // 结束
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[][]{{0,1,0},{0,0,1},{1,1,1},{0,0,0}}, new int[][]{{0,0,0},{1,0,1},{0,1,1},{0,1,0}});
        solution.assertExpected(new int[][]{{1,1},{1,0}}, new int[][]{{1,1},{1,1}});
    }
}
